◀ Prev · Parts · Full · Next ▶

• Both Prim's algorithm and Kruskal's algorithm require processes to know the state of the whole graph, which is very difficult to discover in the message-passing model.

Due to these difficulties, new techniques were needed for distributed MST algorithms in the message-passing model. Some bear similarities to Borůvka's algorithm for the classical MST problem.

The GHS algorithmcite-ref-ghs-1-1[1] of Gallager, Humblet and Spira is one of the best-known algorithms in distributed computing theory. This algorithm constructs an MST in the asynchronous message-passing model.

The GHS algorithm requires several assumptions.

• The input graph is connected and undirected.

• Each edge in the input graph has distinct finite weights. This assumption is not needed if there is a consistent method to break ties between edge weights.

• Each node initially knows the weight of each edge incident to that node.

• Initially, each node is in an inactive state. Each node either spontaneously awakens or is awakened by receipt of any message from another node.

• Messages can be transmitted independently in both directions on an edge and arrive after an unpredictable but finite delay, without error.

• Each edge delivers messages in FIFO order.

Define a fragment of an MST T {\displaystyle T} to be a sub-tree of T {\displaystyle T} . That is, a fragment is a connected set of nodes and edges of T {\displaystyle T} . MSTs have two important properties in relation to fragments:cite-ref-ghs-1-2[1]

◀ Prev · Parts · Full · Next ▶